/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.plan.scale;

import org.mmtk.plan.Plan;
import org.mmtk.plan.TransitiveClosure;
import org.mmtk.plan.scale.utils.ColorMarkSweepMarkBits;
import org.mmtk.plan.scale.utils.ScaleLogger;
import org.mmtk.policy.SegregatedFreeListSpace;
import org.mmtk.utility.Constants;
import org.mmtk.utility.Log;
import org.mmtk.utility.alloc.BlockAllocator;
import org.mmtk.utility.heap.FreeListPageResource;
import org.mmtk.utility.heap.Map;
import org.mmtk.utility.heap.VMRequest;
import org.mmtk.utility.options.EagerCompleteSweep;
import org.mmtk.utility.options.Options;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Inline;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.AddressArray;
import org.vmmagic.unboxed.Extent;
import org.vmmagic.unboxed.ObjectReference;
import org.vmmagic.unboxed.Word;

/**
 * Each instance of this class corresponds to one mark-sweep *space*.
 * Each of the instance methods of this class may be called by any
 * thread (i.e. synchronization must be explicit in any instance or
 * class method).  This contrasts with the MarkSweepLocal, where
 * instances correspond to *plan* instances and therefore to kernel
 * threads.  Thus unlike this class, synchronization is not necessary
 * in the instance methods of MarkSweepLocal.
 */
@Uninterruptible
public final class ScaleMarkSweepSpace extends SegregatedFreeListSpace implements Constants {

  /****************************************************************************
   *
   * Class variables
   */
  /**
   * Select between using mark bits in a side bitmap, or mark bits
   * in the headers of object (or other sub-class scheme), and a single
   * mark bit per block.
   */
  public static final boolean HEADER_MARK_BITS = VM.config.HEADER_MARK_BITS;
  /** highest bit bits we may use */
  private static final int MAX_BITS = 4;

  /* mark bits */
  private static final int COUNT_BASE = 0;
  public static final int DEFAULT_MARKCOUNT_BITS = 2;
  public static final int MAX_MARKCOUNT_BITS = MAX_BITS;
  public static final Word UNLOGGED_BIT = Word.one().lsh(MAX_BITS - 1).lsh(COUNT_BASE);
  public static final Word MARK_COUNT_INCREMENT = Word.one().lsh(COUNT_BASE);
  public static final Word MARK_COUNT_MASK = Word.one().lsh(MAX_MARKCOUNT_BITS).minus(Word.one()).lsh(COUNT_BASE);
  public static final Word MARK_BITS_MASK = Word.one().lsh(MAX_BITS).minus(Word.one());

  private static final boolean EAGER_MARK_CLEAR = Plan.NEEDS_LOG_BIT_IN_HEADER;
  
  /* header requirements */
  public static final int LOCAL_GC_BITS_REQUIRED = MAX_BITS;
  public static final int GLOBAL_GC_BITS_REQUIRED = 0;
  public static final int GC_HEADER_WORDS_REQUIRED = 0;

  /****************************************************************************
   *
   * Instance variables
   */
  private Word markState = Word.one();
  private Word allocState = Word.zero();
  private boolean inMSCollection;
  private static final boolean usingStickyMarkBits = VM.activePlan.constraints().needsLogBitInHeader(); /* are sticky mark bits in use? */
  //private boolean isAgeSegregated = false; /* is this space a nursery space? */
  
  private int MAX_REGIONS = 40;
  private int numRegions;
  public int getNumRegions() {
	  return this.numRegions;
  }
  private AddressArray regionStart;
  public Address getRegionStart(int num) {
	  if(num >= 0 && num < this.numRegions) {
		  return this.regionStart.get(num);
	  } 
	  return Address.zero();
  }
  private AddressArray regionEnd;
  public Address getRegionEnd(int num) {
	  if(num >= 0 && num < this.numRegions) {
		  return this.regionEnd.get(num);
	  } 
	  return Address.zero();
  }
  public long getRegionSize(int num) {
	  if(num >= 0 && num < this.numRegions) {
		  return getRegionEnd(num).toLong() - getRegionStart(num).toLong();
	  } 
	  return 0;
  }
  
  public int getColor(ObjectReference object) {
	  return VM.objectModel.readAvailableBitsWord(object).and(MARK_COUNT_MASK).toInt();
  }
  /****************************************************************************
   *
   * Initialization
   */

  static {
    Options.colorMarkSweepMarkBits = new ColorMarkSweepMarkBits();
    Options.eagerCompleteSweep = new EagerCompleteSweep();
  }

  /**
   * The caller specifies the region of virtual memory to be used for
   * this space.  If this region conflicts with an existing space,
   * then the constructor will fail.
   *
   * @param name The name of this space (used when printing error messages etc)
   * @param pageBudget The number of pages this space may consume
   * before consulting the plan
   * @param vmRequest An object describing the virtual memory requested.
   */
  public ScaleMarkSweepSpace(String name, int pageBudget, VMRequest vmRequest) {
    super(name, pageBudget, 0, vmRequest);
    if (usingStickyMarkBits) allocState = allocState.or(UNLOGGED_BIT);
    this.regionStart = AddressArray.create(MAX_REGIONS);
    this.regionEnd = AddressArray.create(MAX_REGIONS);
  }
  
  private void scanHeap(Scanner scanner, int scan) {
		scanner.start(markState.toInt() - 1, scan);

		if(Options.scaleDebug.getValue() > 5) {
			printVMMap();
		}
		
		Address end;
		if (contiguous) {
			end = start.plus(extent.minus(1));
			scanHeapRegion(scanner, start, end);
			this.numRegions = 1;
			this.regionStart.set(0, start);
			this.regionEnd.set(0, end);	
		} else {
			Address region = lastDiscontiguousRegion;
			int regions = 0;
			while (!region.isZero()) {			
				end = region.plus(Map.getContiguousRegionSize(region).minus(1));
				if(regions < MAX_REGIONS) {
					this.regionStart.set(regions, region);
					this.regionEnd.set(regions, end);						
				} 
				regions++;
				scanHeapRegion(scanner, region, end);
				region = Map.getNextContiguousRegion(region);
				if(region == lastDiscontiguousRegion) {
					break;
				}
			}
			if (regions < MAX_REGIONS) {
				this.numRegions = regions;
			} else {
				if(Options.scaleDebug.getValue() > 3) {
					  Log.write("scanHeap - !!! more regions than allowed, regions=");
					  Log.writeln(regions);
					  Log.flush();
				}	
				this.numRegions = MAX_REGIONS;
			}
		}

		scanner.end();
	}
  
  private static boolean first;
  private static final int ALLIGNMENT = 4;
  private static final int VALID_ALLIGNMENT = 16;
  static final Word ALLIGNMENT_MASK = Word.fromIntSignExtend(1).lsh(2);
  private void scanHeapRegion(Scanner scanner, Address start, Address end){
	  if (Options.scaleDebug.getValue() > 3) {
		  Log.write("scanHeapRegion - enter, start=");
		  Log.write(start);
		  Log.write(", end=");
		  Log.writeln(end);
		  Log.flush();
	  }
	  
	  long addresses = 0;
	  long validObjects = 0;
	  int color;
	  Address address = start;
	  ObjectReference objRef;	  
	  while(address.LT(end)) {
		  addresses++;
		  //objRef = VM.objectModel.getObjectFromStartAddress(address);
		  objRef = address.toObjectReference();	  
		  	  	  
		  if (Options.scaleDebug.getValue() > 9) {
			  Log.write("scanHeapRegion - address=");
			  Log.write(address);
			  Log.write(", objRef=");
			  Log.writeln(objRef);
			  Log.flush();
		  }
		  
		  if(VM.objectModel.validRef(objRef)) {
			  validObjects++;
			  color = VM.objectModel.readAvailableBitsWord(objRef).and(MARK_COUNT_MASK).toInt();
			  if(scanner.scanCell(objRef, color)) {
				  address = VM.objectModel.getObjectEndAddress(objRef).plus(VALID_ALLIGNMENT);
			  } else {
				  address = address.plus(ALLIGNMENT);	
			  }
		  }	 else {
			  if (Options.scaleDebug.getValue() > 9) {
				  Log.write(" ");
				  Log.flush();
				  VM.objectModel.dumpObject(objRef);
				  Log.flush();
			  }		  
			  address = address.plus(ALLIGNMENT);	
		  }		
		  
		  if (Options.scaleDebug.getValue() > 9) {
			  Log.write(", new address=");
			  Log.writeln(address);
			  Log.flush();
		  }
	  }
	  
	  if (Options.scaleDebug.getValue() > 3) {
		  Log.write("scanHeapRegion addresses=");
		  Log.write(addresses);
		  Log.write(", validObjects=");
		  Log.writeln(validObjects);
		  Log.flush();
		  addresses = 0;
		  validObjects = 0;
	  }
  }
  
  //Kathy
  @Override
  public boolean validRef(ObjectReference object) {
	  if(!Scale.isInitialized()) {
		  return true;
	  }
	  int color = VM.objectModel.readAvailableBitsWord(object).and(MARK_COUNT_MASK).toInt();
	    if(color < 0 || color > 3) {
	    	if (Options.scaleDebug.getValue() > 2) {
		    	Log.write("ScaleMarkSweepSpace.validRef, invalid: object=");
		  	  	Log.writeln(object);
		    	Log.write(", color=");
		  	  	Log.writeln(color);
		  	  	Log.flush();
	    	}
	    	return false;
	    }
	    
	    int kathy = VM.objectModel.getKathy(object).toAddress().toInt();
	    if(first && kathy != 0) {
	    	if (Options.scaleDebug.getValue() > 2) {
		    	Log.write("ScaleMarkSweepSpace.validRef, invalid: object=");
		  	  	Log.writeln(object);
		    	Log.write(", kathy=");
		  	  	Log.writeln(kathy);
		  	  	Log.flush();
	    	}
	    	return false;
	    }
	    if(Options.scColors != null) {
		    if(kathy < 0 || kathy > Options.scColors.getValue()) {
		    	if (Options.scaleDebug.getValue() > 2) {
			    	Log.write("ScaleMarkSweepSpace.validRef, invalid: object=");
			  	  	Log.writeln(object);
			    	Log.write(", kathy=");
			  	  	Log.writeln(kathy);
			  	  	Log.flush();
		    	}
		    	return false;
		    }
	    }
	    
	    return true;
  }

  /**
   * Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects?
   */
  @Inline
  protected boolean maintainSideBitmap() {
    return !HEADER_MARK_BITS;
  }

  /**
   * Do we need to preserve free lists as we move blocks around.
   */
  @Inline
  protected boolean preserveFreeList() {
    return !LAZY_SWEEP;
  }

  /****************************************************************************
   *
   * Allocation
   */

  /**
   * Prepare the next block in the free block list for use by the free
   * list allocator.  In the case of lazy sweeping this involves
   * sweeping the available cells.  <b>The sweeping operation must
   * ensure that cells are pre-zeroed</b>, as this method must return
   * pre-zeroed cells.
   *
   * @param block The block to be prepared for use
   * @param sizeClass The size class of the block
   * @return The address of the first pre-zeroed cell in the free list
   * for this block, or zero if there are no available cells.
   */
  protected Address advanceToBlock(Address block, int sizeClass) {
    if (HEADER_MARK_BITS) {
      if (inMSCollection) markBlock(block);
    }

    if (LAZY_SWEEP) {
      return makeFreeList(block, sizeClass);
    } else {
      return getFreeList(block);
    }
  }

  /**
   * Notify that a new block has been installed. This is to ensure that
   * appropriate collection state can be initialized for the block
   *
   * @param block The new block
   * @param sizeClass The block's sizeclass.
   */
  protected void notifyNewBlock(Address block, int sizeClass) {
    if (HEADER_MARK_BITS) {
      if (inMSCollection) markBlock(block);
    }
  }

  /****************************************************************************
   *
   * Collection
   */

  /**
   * Prepare for a new collection increment.  For the mark-sweep
   * collector we must flip the state of the mark bit between
   * collections.
   *
   * @param gcWholeMS True if we are going to collect the whole marksweep space
   */
  /*
  public void prepare(boolean gcWholeMS, boolean firstInCycle) {
	  first = firstInCycle;
	  scanHeap();
	  
    if (HEADER_MARK_BITS && Options.eagerCompleteSweep.getValue()) {
      consumeBlocks();
    } else {
      flushAvailableBlocks();
    }
    if (HEADER_MARK_BITS) {
      if (gcWholeMS) {
        allocState = markState;
        if (usingStickyMarkBits && !isAgeSegregated) // if true, we allocate as "mature", not nursery 
          allocState = allocState.or(UNLOGGED_BIT);
        markState = deltaMarkState(true);
        if (EAGER_MARK_CLEAR)
          clearAllBlockMarks();
      }
    } else {
      zeroLiveBits(start, ((FreeListPageResource) pr).getHighWater());
    }
    inMSCollection = true;
  }*/
  
  public void scan(Scanner scanner, int scan) {
	  if(scanner != null) {
		  scanHeap(scanner, scan);
	  }
  }
  
  public void prepare(boolean gcWholeMS, boolean firstInCycle) {
	  first = firstInCycle;
	   
    if (HEADER_MARK_BITS && Options.eagerCompleteSweep.getValue()) {
      consumeBlocks();
    } else {
      flushAvailableBlocks();
    }
    if (HEADER_MARK_BITS) {
      if (gcWholeMS) {
        //allocState = markState;
        //if (usingStickyMarkBits && !isAgeSegregated) /* if true, we allocate as "mature", not nursery */
        //  allocState = allocState.or(UNLOGGED_BIT);
    	  if(firstInCycle) {
    		  markState = Word.one();
    	  } else {
    		  markState = deltaMarkState(true);
    	  }
        if (EAGER_MARK_CLEAR)
          clearAllBlockMarks();
      }
    } else {
      zeroLiveBits(start, ((FreeListPageResource) pr).getHighWater());
    }
    inMSCollection = true;
  }

  /**
   * A new collection increment has completed.  For the mark-sweep
   * collector this means we can perform the sweep phase.
 */
  public void release() {
    sweepConsumedBlocks(!EAGER_MARK_CLEAR);
    inMSCollection = false;
  }
  
  /**
   * A new collection increment has completed.  For the mark-sweep
   * collector this means we can perform the sweep phase.
 */
  public void release(Sweeper sweeper) {
	  if(sweeper == null) {		  
		  sweepConsumedBlocks(!EAGER_MARK_CLEAR);		  
	  } else {
		  sweeper.start();
		  sweepConsumedBlocks(!EAGER_MARK_CLEAR, sweeper);
		  sweeper.end();
	  }
	  inMSCollection = false;
  }

  /**
   * Release an allocated page or pages
   *
   * @param start The address of the start of the page or pages
   */
  @Inline
  public void release(Address start) {
    ((FreeListPageResource) pr).releasePages(start);
  }

  /**
   * Should the sweep reclaim the cell containing this object. Is this object
   * live. This is only used when maintainSideBitmap is false.
   *
   * @param object The object to query
   * @return True if the cell should be reclaimed
   */
  @Inline
  protected boolean isCellLive(ObjectReference object) {
    if (!HEADER_MARK_BITS) {
      return super.isCellLive(object);
    }
    return testMarkState(object, markState);
  }

  /****************************************************************************
   *
   * Object processing and tracing
   */

  /**
   * Trace a reference to an object under a mark sweep collection
   * policy.  If the object header is not already marked, mark the
   * object in either the bitmap or by moving it off the treadmill,
   * and enqueue the object for subsequent processing. The object is
   * marked as (an atomic) side-effect of checking whether already
   * marked.
   *
   * @param object The object to be traced.
   * @return The object (there is no object forwarding in this
   * collector, so we always return the same object: this could be a
   * void method but for compliance to a more general interface).
   */
  @Inline
  public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) {
    if (HEADER_MARK_BITS) {
      Word markValue = Plan.NEEDS_LOG_BIT_IN_HEADER ? markState.or(Plan.UNLOGGED_BIT) : markState;
      if (testAndMark(object, markValue.toInt())) {
        markBlock(object);
        trace.processNode(object);
      }
    } else {
      if (testAndSetLiveBit(object)) {
        trace.processNode(object);
      }
    }
    return object;
  }
  
  @Inline
	public boolean markObject(ObjectReference object) {
		boolean result = false;

		if (HEADER_MARK_BITS) {
			Word markValue = Plan.NEEDS_LOG_BIT_IN_HEADER ? markState
					.or(Plan.UNLOGGED_BIT) : markState;
			if (testAndMark(object, markValue.toInt())) {
				markBlock(object);
				result = true;
			}
		} else {
			if (testAndSetLiveBit(object)) {
				result = true;
			}
		}

		return result;
	}
  
  public boolean testMarkValue(ObjectReference object, int value) {
		boolean result = false;
		int oldValue = VM.objectModel.readAvailableByte(object);
		int markBits = oldValue & MARK_BITS_MASK.toInt();
		if (markBits == value) {
			result = true;
		}
		return result;
	}

  /**
   *
   * @param object The object in question
   * @return True if this object is known to be live (i.e. it is marked)
   */
  @Inline
  public boolean isLive(ObjectReference object) {
    if (HEADER_MARK_BITS) {
      return testMarkState(object, markState);
    } else {
      return liveBitSet(object);
    }
  }

  /**
   * Get the current mark state
   *
   * @return The current mark state.
   */
  @Inline
  public Word getMarkState() {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markState.and(MARK_COUNT_MASK.not()).isZero());
    return markState;
  }
  
  /**
   * Get the current alloc state
   *
   * @return The current mark state.
   */
  @Inline
  public Word getAllocState() {
    return allocState;
  }

  /**
   * Get the previous mark state.
   *
   * @return The previous mark state.
   */
  @Inline
  public Word getPreviousMarkState() {
    return deltaMarkState(false);
  }

  /**
   * Return the mark state incremented or decremented by one.
   *
   * @param increment If true, then return the incremented value else return the decremented value
   * @return the mark state incremented or decremented by one.
   */
  private Word deltaMarkState(boolean increment) {
    Word mask = Word.fromIntZeroExtend((1 << Options.colorMarkSweepMarkBits.getValue()) - 1).lsh(COUNT_BASE);
    Word rtn = increment ? markState.plus(MARK_COUNT_INCREMENT) : markState.minus(MARK_COUNT_INCREMENT);
    rtn = rtn.and(mask);
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markState.and(MARK_COUNT_MASK.not()).isZero());
    return rtn;
  }

  /****************************************************************************
   *
   * Header manipulation
   */

  /**
   * Perform any required post allocation initialization
   *
   * @param object the object ref to the storage to be initialized
   */
  @Inline
  public void postAlloc(ObjectReference object) {
    initializeHeader(object, true);
  }

  /**
   * Perform any required post copy (i.e. in-GC allocation) initialization.
   * This is relevant (for example) when MS is used as the mature space in
   * a copying GC.
   *
   * @param object the object ref to the storage to be initialized
   * @param majorGC Is this copy happening during a major gc?
   */
  @Inline
  public void postCopy(ObjectReference object, boolean majorGC) {
    initializeHeader(object, false);
    if (!HEADER_MARK_BITS) {
      testAndSetLiveBit(object);
    }
  }

  /**
   * Perform any required initialization of the GC portion of the header.
   *
   * @param object the object ref to the storage to be initialized
   * @param alloc is this initialization occuring due to (initial) allocation
   * (true) or due to copying (false)?
   */
  @Inline
  public void initializeHeader(ObjectReference object, boolean alloc) {
    if (HEADER_MARK_BITS) {
      if (alloc) {
        writeAllocState(object);
      } else {
        writeMarkState(object);
      }
    }
  }

  /**
	 * Atomically attempt to set the mark bit of an object. Return true if
	 * successful, false if the mark bit was already set.
	 * 
	 * @param object The object whose mark bit is to be written
	 * @param value The value to which the mark bits will be set
	 */
	@Inline
	private static boolean testAndMark(ObjectReference object, int value) {
		int oldValue = VM.objectModel.readAvailableByte(object);
		int markBits = oldValue & MARK_BITS_MASK.toInt();
		if (markBits == value) {
			return false;
		}
		byte param = (byte) (oldValue & ~MARK_BITS_MASK.toInt() | value);
		//Log.write("MarkSweepSpace.testAndMark, value=");Log.write(value);
		//Log.write(", oldValue=");Log.write(oldValue);
		//Log.write(", markBits=");Log.write(markBits);
		//Log.write(", param=");Log.writeln(param);
		VM.objectModel.writeAvailableByte(object, param);
		return true;
	}

  /**
   * Return true if the mark count for an object has the given value.
   *
   * @param object The object whose mark bit is to be tested
   * @param value The value against which the mark bit will be tested
   * @return True if the mark bit for the object has the given value.
   */
  @Inline
  public static boolean testMarkState(ObjectReference object, Word value) {
    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(value.and(MARK_COUNT_MASK.not()).isZero());
    return VM.objectModel.readAvailableBitsWord(object).and(MARK_COUNT_MASK).EQ(value);
  }

  /**
   * Write the allocState into the mark state fields of an object non-atomically.
   * This is appropriate for allocation time initialization.
   *
   * @param object The object whose mark state is to be written
   */
  @Inline
  public void writeAllocState(ObjectReference object) {
    Word oldValue = VM.objectModel.readAvailableBitsWord(object);
    Word newValue = oldValue.and(MARK_BITS_MASK.not()).or(allocState);
    VM.objectModel.writeAvailableBitsWord(object, newValue);
  }

  /**
   * Write the markState into the mark state fields of an object non-atomically.
   * This is appropriate for collection time initialization.
   *
   * @param object The object whose mark state is to be written
   */
  @Inline
  private void writeMarkState(ObjectReference object) {
    Word oldValue = VM.objectModel.readAvailableBitsWord(object);
    Word newValue = oldValue.and(MARK_BITS_MASK.not()).or(markState);
    VM.objectModel.writeAvailableBitsWord(object, newValue);
  }
  
  public ObjectReference getAnyValidObject(long seed) {
	  int random = (int)(VM.statistics.nanoTime()*seed);
	  int sizeClass = random%sizeClassCount();
	  sizeClass = (sizeClass >= 0) ? sizeClass : -sizeClass;
	  ObjectReference result = findValidObject(sizeClass);
	  if (Options.verbose.getValue() >= 5) {
		  ScaleLogger.acquireLogLock();
		  Log.prependThreadId();
		  Log.write("getAnyLiveObject, sizeClass=");
		  Log.write(sizeClass);
		  Log.write(", sizeClassCount()=");
		  Log.write(sizeClassCount());
		  Log.write(" result=");
		  Log.flush();
		  VM.objectModel.dumpObject(result);
		  ScaleLogger.releaseLogLock();
	  }
       
	  return result;
  }
  
  private ObjectReference findValidObjectInBlock(Address block, int sizeClass) {
		ObjectReference result = ObjectReference.nullReference();

		Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
		Address cursor = block.plus(blockHeaderSize[sizeClass]);
		Address end = block.plus(blockSize);
		Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
		ObjectReference current;
		int color;
		while (cursor.LT(end)) {
			current = VM.objectModel.getObjectFromStartAddress(cursor);
			if (!current.isNull() 
					&& VM.objectModel.validRef(current) 
					&& !VM.objectModel.isArray(current)
					&& !VM.objectModel.isPrimitiveArray(current)				
					&& !isLive(current)
					&& VM.objectModel.getKathy(current) == ObjectReference.nullReference() 
					&& VM.objectModel.getNumberOfChildren(current) > 0) {
				color = VM.objectModel.readAvailableBitsWord(current).and(MARK_COUNT_MASK).toInt();
				if(color == 0) {
					ScaleLogger.acquireLogLock();
					  Log.prependThreadId();
					  Log.write("findValidObjectInBlock !!! dead root: ");
					  Log.flush();
					  VM.objectModel.dumpObject(result);
					  ScaleLogger.releaseLogLock();
				}
				result = current;
				break;
			}
			cursor = cursor.plus(cellExtent);
		}

		return result;
	}
  
  public ObjectReference findRootCandidate(Address address, int skip) {
		ObjectReference result = ObjectReference.nullReference();
		
		Address block = BlockAllocator.getBlkStart(address);
		
		if(!BlockAllocator.checkBlockMeta(block)) {
			return result;
		}
		int sizeClass = BlockAllocator.getClientSizeClass(address);
		if(sizeClass < 0 || sizeClass >= sizeClassCount()) {
			return result;
		}
		
		Extent blockSize = Extent.fromIntSignExtend(BlockAllocator.blockSize(blockSizeClass[sizeClass]));
		Address cursor = block.plus(blockHeaderSize[sizeClass]);
		Address end = block.plus(blockSize);
		Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
		ObjectReference current;
		while (cursor.LT(end)) {
			current = VM.objectModel.getObjectFromStartAddress(cursor);
			if (current.isNull() || !VM.objectModel.validRef(current)) {
				//invalid object, will not find anything good in this block
				return result;
			}
			
			//valid object, can be root
			if( !VM.objectModel.isArray(current) && 
				!VM.objectModel.isPrimitiveArray(current) && 				
				!isLive(current) && 
				VM.objectModel.getKathy(current) == ObjectReference.nullReference()) {
					if (Options.scaleDebug.getValue() > 5) {
						ScaleLogger.acquireLogLock();
						Log.prependThreadId();
						Log.write("findRootCandidate candidate=");
						Log.flush();
						VM.objectModel.dumpObject(current);
						ScaleLogger.releaseLogLock();
					}
					// lock just to be able to see printouts
					ScaleLogger.acquireLogLock();
					if(VM.objectModel.isRecursive(current, this.descriptor)) {
						result = current;
						ScaleLogger.releaseLogLock();
						break;
					}
					ScaleLogger.releaseLogLock();
			}
			for(int i = 0; i < skip; i++) {
				cursor = cursor.plus(cellExtent);
			}
		}

		return result;
	}
  
  private ObjectReference findValidObjectInBlocks(Address block, int sizeClass) {
		ObjectReference result = ObjectReference.nullReference();
		
		while (!block.isZero()) {
			if (Options.verbose.getValue() >= 5) {
				ScaleLogger.acquireLogLock();
				  Log.prependThreadId();
				  Log.write("findValidObjectInBlocks, block=");
				  Log.write(block);
				  Log.write(", sizeClass");
				  Log.writeln(sizeClass);
				  ScaleLogger.releaseLogLock();
			 }
			Address next = BlockAllocator.getNext(block);
			result = findValidObjectInBlock(block, sizeClass);
			if (result != null) {
				break;
			}
			block = next;
		}

		return result;
	}
  
  private ObjectReference findValidObject(int startSizeClass) {
		ObjectReference result = ObjectReference.nullReference();
		int sizeClass = startSizeClass + 1;
		
		if (Options.verbose.getValue() >= 5) {
			ScaleLogger.acquireLogLock();
			  Log.prependThreadId();
			  Log.write("findValidObject, sizeClass=");
			  Log.writeln(sizeClass);
			  ScaleLogger.releaseLogLock();
		 }
		
		while (sizeClass != startSizeClass) {
			/* Consumed blocks */
			result = findValidObjectInBlocks(consumedBlockHead.get(sizeClass),
					sizeClass);
			if (result != null) {
				if (Options.verbose.getValue() >= 5) {
					ScaleLogger.acquireLogLock();
					  Log.prependThreadId();
					  Log.write("findValidObject, found object in consumedBlockHead, sizeClass=");
					  Log.writeln(sizeClass);
					  ScaleLogger.releaseLogLock();
				 }
				break;
			}
			
			/* available blocks 
			result = findValidObjectInBlocks(availableBlockHead.get(sizeClass),sizeClass);
			if (result != null) {
				if (Options.verbose.getValue() >= 1) {
					  CM.acquireLogLock();
					  Log.prependThreadId();
					  Log.write("findValidObject, found object in availableBlockHead, sizeClass=");
					  Log.writeln(sizeClass);
					  CM.releaseLogLock();
				 }
				break;
			}*/

			/* Flushed blocks 
			result = findValidObjectInBlocks(flushedBlockHead.get(sizeClass), sizeClass);
			if (result != null) {
				if (Options.verbose.getValue() >= 1) {
					  CM.acquireLogLock();
					  Log.prependThreadId();
					  Log.write("findValidObject, found object in flushedBlockHead, sizeClass=");
					  Log.writeln(sizeClass);
					  CM.releaseLogLock();
				 }
				break;
			}*/

			sizeClass++;
			if (sizeClass == sizeClassCount()) {
				sizeClass = 0;
			}
		}

		return result;
	}
}
